﻿#include "pch.h"
#include "CppUnitTest.h"
#include "../ForTest.h"

using namespace Microsoft::VisualStudio::CppUnitTestFramework;



namespace PreSuff3 {
	
	TEST_CLASS(P10429)
	{
		//P10429 [蓝桥杯 2024 省 B] 拔河
		class Solution {
		public:
			long long Ans(vector<int>& a) {
				const int N = a.size();
				vector<long long> preSum(1);
				for (const auto& i : a) { preSum.emplace_back(i + preSum.back()); }
				set<long long> que1;
				long long ans = LLONG_MAX / 2;
				for (int i = 0; i < N; i++) {
					for (int j = i; j < N; j++) {
						auto cur = preSum[j + 1] - preSum[i];
						auto it = que1.lower_bound(cur);
						if (que1.end() != it) {
							ans = min(ans, *it - cur);
						}
						if (que1.begin() != it) {
							--it; ans = min(ans, cur - *it);
						}
					}
					for (int j = 0; j <= i; j++) {
						que1.emplace(preSum[i + 1] - preSum[j]);
					}
				}
				return ans;
			}
		};
	public:
		vector<int> a;	
		TEST_METHOD(TestMethod11)
		{
			a = { 10,9,8,12,14 };
			auto res = Solution().Ans(a);
			AssertEx(1LL, res);
		}
	};

	TEST_CLASS(P7623)
	{
		//【 逆元 前后缀分解】P7623 [AHOI2021初中组] 收衣服|普及+
		typedef C1097Int<998244353> BI;
		class Solution {
		public:
			int Ans(const int N, vector<vector<int>>& W) {
				BI asn;
				vector<BI> pre(N + 1,1), suff(N + 2,1);
				for (int i = 1; i <= N; i++) {
					pre[i] = pre[i - 1] * i;
				}
				for (int i = N; i >= 1; i--) {
					suff[i] = suff[i + 1] * i;
				}
				for (int i = 0; i+1 < N; i++) {
					BI ws = accumulate(W[i].begin(), W[i].end(), BI(0));
					asn += ws * pre[N - 1 - i] * suff[N + 1-i];
				}
				return asn.ToInt();
			}
		};
	public:
		int N;
		vector<vector<int>> W;
		TEST_METHOD(TestMethod11)
		{
			N = 5, W = { {1,2,3,4,5},{1,2,3,4},{1,2,3},{1,2} };
			auto res = Solution().Ans(N,W);
			AssertEx(1080, res);
		}
	};
	TEST_CLASS(P9255)
	{
		//【前后缀分解】P9255 [PA 2022] Podwyżki|普及+
		class Solution {
		public:
			vector<int> Ans(const int N, vector<int>& a,const int K) {
				if (K >= 4) {
					for (int i = 0; i < N - 1; i++) {
						if (a[i] >= a[i + 1]) {
							vector<int> ans;
							const bool bEnd = (i + 2 == N);
							for (int j = 0; j < i; j++) {
								if ((ans.size() + (3+ (!bEnd)) < K) && (i - j > 1)) {
									ans.emplace_back(j + 1);
								}
								else {
									ans.emplace_back(i); break;
								}
							}
							ans.emplace_back(i + 1);	
							if (!bEnd)
							{
								ans.emplace_back(i + 2);
							}
							for (int j = i + 2; j < N; j++) {
								if (ans.size() + 1 == K) { break; }
								ans.emplace_back(j + 1);
							}
							return ans;
						}						
					}				
					return {};
				}
				vector<int> pre(N + 1, INT_MAX / 2), suff(N + 1, INT_MIN / 2);
				for (int i = 1; i <= N; i++) {
					pre[i] = min(pre[i - 1], a[i-1]);
					suff[i] = max(suff[i - 1], a[N - i]);
				}
				if (3 == K) {
					for (int i = 1; i < N - 1; i++) {
						if ((a[i] <= pre[i]) || (a[i] >= suff[N - i - 1])) {
							return { i,i + 1 };
						}
					}
					return {};
				}
				for (int i = 1; i < N; i++) {
					if (pre[i] >= suff[N - i]) { 
						return { i }; }
				}
				return {};
			}
		};
	public:
		vector<int> a;
		TEST_METHOD(TestMethod11)
		{
			a = { 1,2,3,4,4,5,6 };
			auto res = Solution().Ans(a.size(),a,6);
			AssertEx({1,2,3,4,5}, res);
		}
		TEST_METHOD(TestMethod12)
		{
			a = { 1,2,3,4,4,5,6 };
			auto res = Solution().Ans(a.size(), a, 7);
			AssertEx({ 1,2,3,4,5,6 }, res);
		}
		TEST_METHOD(TestMethod13)
		{
			a = { 1,2,3,4,4,5,6 };
			auto res = Solution().Ans(a.size(), a, 5);
			AssertEx({ 1,3,4,5 }, res);
		}
		TEST_METHOD(TestMethod14)
		{
			a = { 1,2,3,4,4,5,6 };
			auto res = Solution().Ans(a.size(), a, 4);
			AssertEx({ 3,4,5 }, res);
		}
		TEST_METHOD(TestMethod15)
		{
			a = { 1,2,3,4,5,6 };
			auto res = Solution().Ans(a.size(), a, 4);
			AssertEx({  }, res);
		}
		TEST_METHOD(TestMethod16)
		{
			a = { 2,4,3,6,7 };
			auto res = Solution().Ans(a.size(), a, 3);
			AssertEx({  }, res);
		}
		TEST_METHOD(TestMethod17)
		{
			a = { 4,3,6,7 };
			auto res = Solution().Ans(a.size(), a, 3);
			AssertEx({ 1,2 }, res);
		}
		TEST_METHOD(TestMethod18)
		{
			a = { 4,3,6,7 };
			auto res = Solution().Ans(a.size(), a, 2);
			AssertEx({  }, res);
		}
		TEST_METHOD(TestMethod19)
		{
			a = { 6,7,3,4 };
			auto res = Solution().Ans(a.size(), a, 2);
			AssertEx({ 2 }, res);
		}
		TEST_METHOD(TestMethod20)
		{
			a = {1,1,2,3 };
			auto res = Solution().Ans(a.size(), a, 4);
			AssertEx({ 1,2,3 }, res);
		}
		TEST_METHOD(TestMethod21)
		{
			a = { 1,2,3,3 };
			auto res = Solution().Ans(a.size(), a, 4);
			AssertEx({ 1,2,3 }, res);
		}
	};

	TEST_CLASS(B4274)
	{
		//【前后缀分解 排序】B4274 [蓝桥杯青少年组省赛 2023] 数字游戏|普及+
		class Solution {
		public:
			tuple<long long,int,int> Ans(const int N, vector<int>& a) {
				sort(a.begin(), a.end());
				auto Pre = [&](const vector<int>& a) {
					vector<long long> ret(2);
					for (int i = 1; i < N; i++) {
						const int add = (a[i] == a[i - 1]) ? 0 : i;
						ret.emplace_back(ret.back() + add);
					}
					return ret;
				};
				auto pre = Pre(a);
				auto suff = Pre(vector<int>(a.rbegin(), a.rend()));
				long long llCnt = LLONG_MAX / 2;
				int mi = -1, ma = -1;
				for (int i = 0; i <= N; i++) {
					auto cur = max(pre[i], suff[N - i])*2;
					if (pre[i] > suff[N - i]) { cur--; }
					if (cur < llCnt) {
						llCnt = cur;
						mi = a[max(0, i - 1)];
						ma = a[min(i, N - 1)];
					}
				}
				return {llCnt,mi,ma};
			}
		};
	public:
		vector<int> a;
		TEST_METHOD(TestMethod11)
		{
			 a = { 1,3,4,2 };
			auto res = Solution().Ans(a.size(), a);
			AssertEx({ 2,2,3 }, res);
		}
		TEST_METHOD(TestMethod12)
		{
			a = {8,7 };
			auto res = Solution().Ans(a.size(), a);
			AssertEx({ 0,7,8 }, res);
		}
	};
}